package leetcode.day_2020_12_07_12_14;

/**
 * 123. 买卖股票的最佳时机 III
 *
 */
public class L_123 {
    public static void main(String[] args) {
        int[] prices = {1,2,3,4,5};
        System.out.println(maxProfit(prices));
    }

    public static int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        int maxK = 2;
        int[][][] dp = new int[n][maxK+1][2];
        for(int i=0; i<n; i++) {
            for (int k=maxK; k>=1; k--){
                if(i-1 == -1) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                } else {
                    dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                    dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
                }
            }
        }
        return dp[n-1][maxK][0];
    }
}
